package demo.hw;

import java.util.Arrays;

/**
 * 【租车骑绿岛】
 * 部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，做最大载重M。
 * 给出部门每个人的体重，请问最多需要租用多少双人自行车。
 * 输入描述：
 * 第一行两个数字m、n,分别代表自行车限重，部门总人数。
 * 第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。
 * 0<m<=200
 * 0<n<=1000000
 * 输出描述：
 * 最小需要的双人自行车数量。
 * 示例1
 * 输入
 * 3 4
 * 3 2 2 1
 * 输出
 * 3
 * <p>
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */
public class _租车 {
    public static void main(String[] args) {
        /*
         * 1.排序：首先将所有人的体重按升序排序。这样我们可以方便地找到最轻和最重的人进行配对。
         * 2.双指针法：使用两个指针，一个指向最轻的人（左指针），一个指向最重的人（右指针）。
         * 如果最轻和最重的人的体重之和不超过M，那么他们可以配对在一辆自行车上，移动两个指针。
         * 如果他们的体重之和超过M，那么最重的人无法与任何人配对（因为最轻的人已经是唯一能尝试配对的），所以最重的人需要单独一辆自行车，移动右指针。
         * 3.计数：每次配对或单独搭载时，自行车数量加1。
         * 算法步骤
         * 对体重数组进行排序。
         * 初始化左指针left = 0，右指针right = n - 1，自行车数量count = 0。
         * 当left <= right时：
         * 如果体重[left] + 体重[right] <= M：
         * 他们可以配对，left++，right--，count++。
         * 否则：
         * 体重[right]太大，无法与任何人配对，right--，count++。
         * 返回count。
         */
        int[] arr = {3, 2, 2, 1};
        Arrays.sort(arr);
        int m = 3;
        int left = 0, right = arr.length - 1;
        int count = 0;
        while (left < right) {
            if (arr[left] + arr[right] <= m) left++;
            right--;
            count++;
        }
        System.out.println(count);
    }
}
